package medium;

import java.util.HashSet;
import java.util.Set;

/*
142. 环形链表 II
解题思路：模拟法
 */
public class LeeCode142 {

  public static void main(String[] args) {

  }

  public ListNode detectCycle(ListNode head) {
    ListNode pos = head;
    Set<ListNode> visited = new HashSet<ListNode>();
    while (pos != null){
      if (visited.contains(pos)){
        return pos;
      }else {
        visited.add(pos);
      }
      pos = pos.next;
    }
    return null;
  }

  class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
      val = x;
      next = null;
    }
  }
}
